package algs4.ds;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ArrayStack<E> extends Stack<E>
{
    /* Innner Class */
    private class StackIterator implements Iterator<E>
    {
        private int i = top;

        public boolean hasNext() { return i > 0;    }
        public E       next()    { return ary[--i]; }
    }

    /* Fields */
    private E[] ary;
    private int top;

    /* Constructors */
    public ArrayStack() { ary = (E[]) new Object[4]; top = 0; }

    /* Instance Methods */
    public boolean     isEmpty()  { return top == 0;           }
    public int         size()     { return top;                }
    public Iterator<E> iterator() { return new StackIterator(); }

    public void push(E e) {
        // if stack is full, then resize the capacity
        if (top == ary.length) resize(2 * top);

        ary[top++] = e;
    }

    public E pop() throws NoSuchElementException {
        // if stack is empty, then throw exception
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");

        // retrieve element
        E e = ary[--top];

        // avoid loitering
        ary[top] = null;

        // if usage rate is less than a quarter, then shrink the capacity
        if (top > 1 && top == ary.length / 4) resize(2 * top);

        return e;
    }

    public E peek() throws NoSuchElementException {
        // if stack is empty throw exception
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");

        return ary[top - 1];
    }

    private void resize(int cap) {
        assert cap >= top;

        E[] dst = (E[]) new Object[cap];
        System.arraycopy(ary, 0, dst, 0, top);
        ary = dst;
    }

    /* Main Test */
    public static void main(String[] args) {
        Stack<Integer> stack = new ArrayStack<>();

        for (int i = 1; i < 100; i++) {
            if (i % 3 == 0) stack.pop();
            else            stack.push(i);
        }

        for (int i : stack)
            System.out.print(i + " ");
        System.out.println();
        System.out.println("size = " + stack.size());
    }
}
